package src.CodeTop;

import java.util.ArrayList;
import java.util.Collections;

/**
 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 *
 * 进阶：
 *
 * 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
 *  
 *
 * 示例 1：
 *
 *
 * 输入：head = [4,2,1,3]
 * 输出：[1,2,3,4]
 * 示例 2：
 *
 *
 * 输入：head = [-1,5,3,4,0]
 * 输出：[-1,0,3,4,5]
 * 示例 3：
 *
 * 输入：head = []
 * 输出：[]
 *
 */

public class _148SortList {
    public static void main(String[] args) {
        int[] nums = {4, 2, 1, 3};
        ListNode head = TestListNode.generateLinkedList(4, nums);
        ListNode target = sortList(head);
        TestListNode.showLinkedList(target);
    }

    public static ListNode sortList(ListNode head) {
        // 校验合法性
        if (head == null || head.next == null)
            return head;
        // 定义集合存储链表数值
        ArrayList<Integer> list = new ArrayList<>();
        // 定义遍历指针
        ListNode cur = head;
        // 遍历链表
        while (cur != null) {
            // 将当前结点的值放入集合中
            list.add(cur.val);
            // 指针后移
            cur = cur.next;
        }
        // 对数值进行排序
        Collections.sort(list);
        // 开辟一个新的头结点
        ListNode newNode = new ListNode(list.get(0));
        // 新链表的尾指针，用于连接新结点
        ListNode combine = newNode;
        // 遍历出剩下的值
        for (int i = 1 ; i < list.size() ; i++) {
            // 生成新的结点
            ListNode node = new ListNode(list.get(i));
            // 尾插到链表中
            combine.next = node;
            // 尾指针后移
            combine = combine.next;
        }
        return newNode;
    }
}
